import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;

import org.ujmp.core.Matrix;
import org.ujmp.core.doublematrix.DoubleMatrix;
import org.ujmp.core.doublematrix.SparseDoubleMatrix;
import org.ujmp.core.doublematrix.impl.DefaultDenseDoubleMatrix2D;
import org.ujmp.core.doublematrix.impl.DefaultSparseDoubleMatrix;

public class PageRank {

	private static final double a = 0.15;
	private static final double eps = 0.0001;

	private HashMap<Integer, Integer> outDegree;
	private HashMap<Integer, HashSet<Integer>> links;
	private int n;
	private DoubleMatrix m;
	private DoubleMatrix r;

	public PageRank() {
		outDegree = new HashMap<Integer, Integer>();
		links = new HashMap<Integer, HashSet<Integer>>();

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		PageRank pr = new PageRank();
		pr.rank();
	}

	public void rank() {
		readFile("dataset/transition.txt");
		buildM();
		initializeR();

		int k = 0;
		DoubleMatrix r2;
		do{
			k++;
			System.out.println("k="+k);
			DoubleMatrix r1 = m.transpose().times(1 - a).mtimes(r)
					.toDoubleMatrix();
			//System.out.println(r1);

			r2 = r1.plus(a / n).toDoubleMatrix();
			//System.out.println(r2);

		}while(!isConverged(r2));
	}

	public void readFile(String fileName) {

		try {
			BufferedReader br = new BufferedReader(new FileReader(fileName));
			String line;
			n = 0;
			while ((line = br.readLine()) != null) {
				String[] str = line.split(" ");
				int i = Integer.parseInt(str[0]);
				int j = Integer.parseInt(str[1]);

				if (i > n) {
					n = i;
				}

				if (j > n) {
					n = j;
				}

				if (!links.containsKey(i)) {
					HashSet<Integer> ends = new HashSet<Integer>();
					ends.add(j);
					links.put(i, ends);
				} else {
					links.get(i).add(j);
				}

				if (outDegree.containsKey(i)) {
					outDegree.put(i, outDegree.get(i) + 1);
				} else {
					outDegree.put(i, 1);
				}
			}

			br.close();
//			System.out.println(outDegree);
//			System.out.println(n);
//			System.out.println(links);
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	/*
	 * initialize PageRnak vector r
	 */
	public void initializeR() {

		r = new DefaultDenseDoubleMatrix2D((long) n, 1L);
		for (int i = 0; i < n; i++) {
			r.setDouble((double) (1.0 / n), (long) i, 0L);
		}
		//System.out.println(r);
	}

	/*
	 * build Link-based Transition Matrix m
	 */
	public void buildM() {

		m = new DefaultSparseDoubleMatrix((long) n, (long) n);
		for (Entry<Integer, HashSet<Integer>> e : links.entrySet()) {
			int i = e.getKey();
			double v = 1.0 / outDegree.get(i);
			for (int j : e.getValue()) {
				m.setDouble(v, (long) (i - 1), (long) (j - 1));
			}
		}
		//System.out.println(m);
	}

	/*
	 * determine whether PageRank vector converges
	 */
	public boolean isConverged(DoubleMatrix r2) {
		//System.out.println("isConverged?");
		//System.out.println(r);
		
		double sum = 0;
		for(int i = 0; i < n; i++){
			sum += Math.abs(r.getDouble((long)i, 0L) - r2.getDouble((long)i, 0L)); 
		}
		r=r2;
		
		System.out.println(sum);
		if(sum < eps)
			return true;
		else
			return false;
	}

}
